package com.sicheng.lc.周赛.分类.贪心.区间问题;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/31 21:28
 */
@SuppressWarnings("all")
public class 区间分组 {
    //https://www.acwing.com/problem/content/908/

    /**
     * 给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
     * <p>
     * 输出最小组数。
     * <p>
     * 输入格式
     * 第一行包含整数 N，表示区间数。
     * <p>
     * 接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
     * <p>
     * 输出格式
     * 输出一个整数，表示最小组数。
     * <p>
     * 数据范围
     * 1≤N≤10e5,
     * −10e9≤ai≤bi≤10e9
     * 输入样例：
     * 3
     * -1 1
     * 2 4
     * 3 5
     * 输出样例：
     * 2
     */

    // 大致思路
    // 将区间按左端点排序
    // 枚举每一个区间看他是否可以加入到某个组里 已生成的组只需维护每个组的区间最右值即可
    // 如何确定呢
    // 1.其实就是已存在的组里满足  当前区间左端点大于这个组的最右值 l[i] > max_r
    // 2.否则就要新开一个组
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] e = new int[n][2];
        for (int i = 0; i < n; i++) {
            e[i][0] = in.nextInt();
            e[i][1] = in.nextInt();
        }
        Arrays.sort(e, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> heap = new PriorityQueue<>((int) 1e4);
        heap.add(Integer.MIN_VALUE);
        for (int[] d : e) {
            boolean ok = false;

            int r = heap.peek();
            if (d[0] > r) {
                heap.remove();
                heap.offer(d[1]);
                ok = true;
            }

            // 和已存在的组不互溶 新开一组
            if (!ok) {
                heap.add(d[1]);
            }
        }

        System.out.println(heap.size());
    }

}
